SAE202 : Exploration algorithmique d'un problème

Par SOUPRAMANIANE Cyril & NEJJARI Abdenour

Dans le cadre de la SAE202 : Exploration algorithmique d'un problème. Il nous a été demandé de réaliser un projet mathématique et informatique. </br> Après concertation avec notre enseignant, nous avons choisi de réaliser le projet Optimisation : Dichotomie.

Niveau : ☆

Description : Nous avons vu en cours que la méthode de la dichotomie est une méthode
permettant de déterminer l'extrema(local) d'une fonction sur un intervalle donné, c'est à dire la valeur de x à laquelle f(x) s'annule.

Animation : Les différentes étapes de l'algorithme sur trois fonctions différentes.

Nous avons travailler environ 16h sur ce projet et avons réparti le travail comme suit :

• Abdenour : "Présentation des bibliothèques et de la méthode de dichotomie." </br>

• Cyril : "Modélisation informatique des fonctions, Création des différents types de fonctions, Animation des fonctions, Limites de la méthode." </br>

Malgré cette division, nous avons participé collègialement à l'intégralité du projet et échanger chacun avec l'autre au travers d'un canal discord privé crée spécialement pour ce travail et par mail.

Les bibliothèques

Voici les bibliothèques dont nous aurons besoin pour le bon fonctionnement de nos programmes de cette SAE.

#Fonction aléatoire
from random import random

#Fonction de graphique et d'animation
from matplotlib.pyplot import *
import numpy as np
from matplotlib import animation
from IPython.display import HTML
import matplotlib.pyplot as plt

Les programmes

Voici les programmes dont nous aurons besoin pour réaliser notre SAE à bien et obtenir les animations attendues

Pour commencer, la dichotomie est une méthode pour trouver une solution approchée à une équation f(x)=0 d'une fonction en répétant des partages d'un intervalle en deux parties puis en sélectionnant le sous-intervalle dans lequel existe le zéro de la fonction.

On considère deux nombres réels a et b et une fonction réelle f continue sur l'intervalle [a, b] telle que f(a) et f(b) soient de signes opposés.

Supposons que nous voulions résoudre l'équation f(x) = 0.

D'après le théorème des valeurs intermédiaires, f a au moins un zéro dans l’intervalle [a, b].

Pour trouver la solution, on divise l'intervalle en deux parties égales avec comme milieu m=(a+b)/2. Il y a maintenant deux possibilités : soit f(a) et f(m) sont de signes contraires, soit f(m) et f(b) sont de signes contraires.

Si f(a)×f(m) on le même signe, la solution se trouve alors dans l'encadrement [m,b] sinon elle se trouve dans l'encadrement [a,m].

On recommence alors la recherche dans le nouveau l'encadrement jusqu'à ce que a−b soit inférieur à la précision souhaiter.

On développe donc la fonction ci-dessous:

#création de la fonction dichotomie

def dichotomie(f, a, b, e):          #la fonction prend en paramètres la fonction, 
                                     #la valeur de a et de b qui sont des encadrements 
                                     #et enfin la valeur de e qui doit être proche de 0 
                                     #car elle nous donne la solution à f(x)=0
        
        
        if f(a)*f(b) > 0:            # On vérifie l'encadrement de la fonction
            print("Le choix de a ou b n'est pas cohérent")
        
        else:                        #on vérifie que f(a) et f(b) sont bien de signes contraires
            
            m = (a + b)/2            #on divise l'intervalle en deux parties égales avec comme milieu m=(a+b)/2
            
            while abs(a - b) > e:    #on répète les cas tant que la valeur absolue de a - b est supérieur à e 
                                     #qui doit être proche de 0,pour obtenir la solution à f(x)=0
                                    
                if f(m) == 0:        #premier cas: si f(m) = 0, alors le milieu correspond à m.
                    return m
                
                elif f(a)*f(m) > 0:  #deuxième cas: si f(m) et f(a) sont de même signe, alors le milieu correspond à a.
                    a = m
                    print("a =", a)
                    print("b =", b)
                
                else:
                    b = m            #dernier cas:le milieu correspond à b.
                    print("a =", a)
                    print("b =", b)
                
                m = (a + b)/2        #on en déduit la solution à f(x)=0 qui est donc m.
            return("La solution à f(x) = 0 est:",m)

Les différents types de fonction

Nous allons tester la méthode de dichotomie sur plusieurs types de fonction.

En effet, certaines fonctions sont monotones donc n'ont aucune solution à f(x)=0.

D'autres ont une solution car elles ont qu'un changement de signe. Et enfin, d'autres ont en plusieurs car plusieurs changements du signes.

Les fonctions à plusieurs solutions

On affecte une fonction mathématique à la fonction dichotomie afin de trouver la valeur de x en laquelle f(x) s'annule.

On cherche à résoudre f(x)=0 avec : f(x)=5x^2−34.

On définit la fonction f(x) dans python.

#création d'une fonction mathématique

def f(x):
    return 5*x**2-34

On trace le graphique de la fonction afin de visualiser sa courbe et de déterminer le nombre de changements de signes qui nous donnera implicitement le nombre de solutions à f(x)=0. On peut donc en apercevoir deux sur cette courbe.

#création du graphique 

x = np.linspace(-4, 4, 100)

plt.plot(x, f(x))
plt.axhline(y=0, color="black")
plt.axvline(x=0, color="black")
plt.grid(True)
plt.xlabel("x")
plt.ylabel("f(x)")
plt.title("Tracé de f(x) = 5x**2-34")
plt.show()

Determination des intervalles de la fonction à plusieurs solutions

On peut voir sur le graphe que la fonction admet deux solutions. On va alors chercher les solutions dans les deux intervalles [-4,-1] et [1,4] en utilisant la méthode de recherche par dichotomie.

ATTENTION: CERTAINS FONCTIONS SONT MONOTONES ET N'ONT DONC PAS DE SOLUTIONS. IL FAUDRA DONC VÉRIFIER QUE LA/LES INTERVALLES EN QUESTION CONTIENNENT UN/DES SOLUTIONS À f(x)=0.

Placement du premier intervalle sur un graphique

On peut voir sur le graphe que la fonction admet deux solutions. On va alors chercher la première solution à f(x) = 0 dans l'intervalle [-4,-1] en utilisant la méthode de recherche par dichotomie.

#création du graphique du premier intervalle

x = np.linspace(-4, -1, 100)

plt.plot(x, f(x))
plt.axhline(y=0, color="black")
plt.axvline(x=0, color="black")
plt.grid(True)
plt.xlabel("x")
plt.ylabel("f(x)")
plt.title("Tracé de f(x) = 5*x**2-34")
plt.show()

Determination de la première solution

On cherche à déterminer la première solution à f(x)=0 à travers l'exécution de la fonction dichotomie.

#détermination de la première solution et de l'intervalle

x1 = dichotomie(f, -4, -1, 0.001)

print(x1)

a = -4
b = -2.5
a = -3.25
b = -2.5
a = -2.875
b = -2.5
a = -2.6875
b = -2.5
a = -2.6875
b = -2.59375
a = -2.640625
b = -2.59375
a = -2.6171875
b = -2.59375
a = -2.6171875
b = -2.60546875
a = -2.611328125
b = -2.60546875
a = -2.6083984375
b = -2.60546875
a = -2.6083984375
b = -2.60693359375
a = -2.6083984375
b = -2.607666015625
('La solution à f(x) = 0 est:', -2.6080322265625)

Placement de la première solution sur un graphique

On va, ensuite, placer la première solution sur la courbe.

#création du graphique de la premiere solution

x = np.linspace(-4, -1, 100)

plt.plot(x, f(x))
line1, = plt.plot(-2.6080322265625,0, marker="o", color="red")
plt.axhline(y=0, color="black")
plt.axvline(x=0, color="black")
plt.grid(True)
plt.xlabel("x")
plt.ylabel("f(x)")
plt.title("Tracé de f(x) = 5x**2-34")
plt.legend([line1],["1ère solution"])
plt.show()

Placement du deuxième intervalle sur un graphique

On réitère l'opération avec le deuxième intervalle en placant déjà le deuxième intervalle.

#création du graphique du deuxième intervalle 

x = np.linspace(1, 4, 100)

plt.plot(x, f(x))
plt.axhline(y=0, color="black")
plt.axvline(x=0, color="black")
plt.grid(True)
plt.xlabel("x")
plt.ylabel("f(x)")
plt.title("Tracé de f(x) = 5*x**2-34")
plt.show()

Determination de la deuxième solution

On va, ensuite, déterminer la deuxième solution qui annule la fonction f(x) en 0 par le biais de la fonction dichotomie.

#détermination de la deuxième solution et de l'intervalle

x2 = dichotomie(f, 1, 4, 0.001)
print(x2)

a = 2.5
b = 4
a = 2.5
b = 3.25
a = 2.5
b = 2.875
a = 2.5
b = 2.6875
a = 2.59375
b = 2.6875
a = 2.59375
b = 2.640625
a = 2.59375
b = 2.6171875
a = 2.60546875
b = 2.6171875
a = 2.60546875
b = 2.611328125
a = 2.60546875
b = 2.6083984375
a = 2.60693359375
b = 2.6083984375
a = 2.607666015625
b = 2.6083984375
('La solution à f(x) = 0 est:', 2.6080322265625)

Placement de la deuxième solution sur un graphique

Puis, enfin, on va placer la deuxième et dernière solution de cette fonction sur la courbe

#création du graphique de la seconde solution

x = np.linspace(1, 4, 100)

plt.plot(x, f(x))
line2, = plt.plot(2.6080322265625,0, marker="o", color="red")
plt.axhline(y=0, color="black")
plt.axvline(x=0, color="black")
plt.grid(True)
plt.xlabel("x")
plt.ylabel("f(x)")
plt.title("Tracé de f(x) = 5*x**2-34")
plt.legend([line2],["2ème solution"])
plt.show()

Placement des deux solutions sur un graphique

On va retracer la courbe en entière avec les deux solutions placées sur cette dernière pour avoir un meilleur visuel sur l'ensemble de la fonction.

#création du graphique 

x = np.linspace(-4, 4, 100)

plt.plot(x, f(x))
line1, = plt.plot(-2.6080322265625,0, marker="o", color="red")
line2, = plt.plot(2.6080322265625,0, marker="o", color="purple")
plt.axhline(y=0, color="black")
plt.axvline(x=0, color="black")
plt.grid(True)
plt.xlabel("x")
plt.ylabel("f(x)")
plt.title("Tracé de f(x) = 5*x**2-34")
plt.legend([line1,line2],["1ère solution","2ème solution"])
plt.show()

Les animations de f(x)=5*x**2-34

Après plusieurs tests, voici quelques animations intéréssantes que nous proposons pour la fonction f(x)=5*x**2-34.

a=-4
b=4
n=250

X=[a+(b-a)*k/n for k in range(n+1)]
Y=[5*x**2-34 for x in X]

title("Réprésentation de la fonction $x\mapsto 5*x**2-34$")
ylim(-40, 40)
xlim(-4, 4)
plot([0, 0], [-40, 40], 'k')
plot([-40, 40], [0,0], 'k')
plot(X, Y, 'r')
line1,=plot(-2.6080322265625,0, marker="o", color="red")
line2,=plot(2.6080322265625,0, marker="o", color="purple")
plt.legend([line1,line2],["1ère solution","2ème solution"])
grid(True)
show()

NUM_FRAME=[n//4, n//2, 3*n//4, n, n+1]
for num_frame in NUM_FRAME : 
    title("Réprésentation de la frame "+str(num_frame)+" la fonction $x\mapsto 5*x**2-34 $")
    ylim(-40, 40)
    xlim(-4, 4)
    plot([0, 0], [-40, 40], 'k')
    plot([-40, 40], [0,0], 'k')
    plot(X[:num_frame], Y[:num_frame], 'r')
    line1,=plot(-2.6080322265625,0, marker="o", color="red")
    line2,=plot(2.6080322265625,0, marker="o", color="purple")
    plt.legend([line1,line2],["1ère solution","2ème solution"])
    grid(True)
    show()

fig = figure() #On donne le nom 'fig' à la fenêtre

f, =plot([], [], 'r', lw=3, label="$f(x)=5*x**2-34$") #On donne le nom 'f' à la courbe de la fonction et on précise toutes les options voulues

title("Représentation de la fonction $5*x**2-34$ sur $[-4 ; 4]$") #On met un titre au graphique
ylim(-40, 40) #On précise le champ des abscices
xlim(-4, 4) #On précise le champ des ordonées

#Axe du repère
plot([0, 0], [-40, 40], 'k')
plot([-40, 40], [0,0], 'k')
plot(-2.6080322265625,0, marker="o", color="red")
plot(2.6080322265625,0, marker="o", color="purple")
legend() #On demande l'affiche des label
grid(True) #On demande l'affichage de la grille

def MonAnimation(num_frame) : 
    f.set_data(X[0:num_frame], Y[0:num_frame])#Pour une liste Z, Z[a:b] renvoie les valeurs de Z entre les positions a et b
    return ()

ani = animation.FuncAnimation(fig, MonAnimation, n+2)#On a n+1 frame, mais il faut rajouter la frame initiale

HTML(ani.to_jshtml())

Once Loop Reflect

Les fonctions à une seule solution dans l'intervalle de gauche

On affecte une fonction mathématique à la fonction dichotomie afin de trouver la valeur de x en laquelle f(x) s'annule.

On cherche à résoudre y(x)=0 avec : y(x)=5x+4.

On définit la fonction y(x) dans python.

#création d'une fonction mathématique

def y(x):
    return 5*x+4

On trace le graphique de la fonction afin de visualiser sa courbe et de déterminer le nombre de changements de signes qui nous donnera implicitement le nombre de solutions à y(x)=0.

#création du graphique 

x = np.linspace(-4, 4, 100)

plt.plot(x, y(x))
plt.axhline(y=0, color="black")
plt.axvline(x=0, color="black")
plt.grid(True)
plt.xlabel("x")
plt.ylabel("y(x)")
plt.title("Tracé de y(x) = 5x+4")
plt.show()

Determination de l'intervalle de la fonction à une solution dans l'intervalle de gauche

On peut voir sur le graphe que la fonction admet une solution. On va alors chercher la solution dans l'intervalle de gauche[-4,0] en utilisant la méthode de recherche par dichotomie.

ATTENTION: CERTAINS FONCTIONS SONT MONOTONES ET N'ONT DONC PAS DE SOLUTIONS. IL FAUDRA DONC VÉRIFIER QUE LA/LES INTERVALLES EN QUESTION CONTIENNENT UN/DES SOLUTIONS À y(x)=0.

Placement de l'intervalle de gauche sur un graphique

On peut voir sur le graphe que la fonction admet une seule solution. On va alors chercher la solution à f(x) = 0 dans l'intervalle [-4,0] en utilisant la méthode de recherche par dichotomie. Tout d'abord, plaçons l'intervalle (de gauche) qui contient la seule solution de la fonction à y(x)=0.

#création du graphique du premier intervalle

x = np.linspace(-4, 0, 100)

plt.plot(x, y(x))
plt.axhline(y=0, color="black")
plt.axvline(x=0, color="black")
plt.grid(True)
plt.xlabel("x")
plt.ylabel("y(x)")
plt.title("Tracé de y(x) = 5*x+4")
plt.show()

Determination de la solution

Puis, determinons la valeur de l'unique solution à y(x)=0 à l'aide de la fonction dichotomie.

#détermination de la première solution et de l'intervalle

x1 = dichotomie(y, -4, 0, 0.001)

print(x1)

a = -2.0
b = 0
a = -1.0
b = 0
a = -1.0
b = -0.5
a = -1.0
b = -0.75
a = -0.875
b = -0.75
a = -0.8125
b = -0.75
a = -0.8125
b = -0.78125
a = -0.8125
b = -0.796875
a = -0.8046875
b = -0.796875
a = -0.80078125
b = -0.796875
a = -0.80078125
b = -0.798828125
a = -0.80078125
b = -0.7998046875
('La solution à f(x) = 0 est:', -0.80029296875)

Placement de la solution sur un graphique

Enfin, plaçons l'unique solution sur son intervalle (de gauche) en premier temps. Puis dans un second temps, plaçons la sur la coube complète pour un meilleur aperçu.

#création du graphique de la premiere solution

x = np.linspace(-4, 0, 100)

plt.plot(x, y(x))
line1, = plt.plot(-0.80029296875,0, marker="o", color="red")
plt.axhline(y=0, color="black")
plt.axvline(x=0, color="black")
plt.grid(True)
plt.xlabel("x")
plt.ylabel("y(x)")
plt.title("Tracé de y(x) = 5x+4")
plt.legend([line1],["Solution"])
plt.show()

#création du graphique 

x = np.linspace(-4, 4, 100)

plt.plot(x, y(x))
line1, = plt.plot(-0.80029296875,0, marker="o", color="red")
plt.axhline(y=0, color="black")
plt.axvline(x=0, color="black")
plt.grid(True)
plt.xlabel("x")
plt.ylabel("f(x)")
plt.title("Tracé de f(x) = 5*x+4")
plt.legend([line1],["Solution"])
plt.show()

Les animations de y(x)=5*x+4

Après plusieurs tests, voici quelques animations intéréssantes que nous proposons pour la fonction y(x)=5*x+4.

a=-4
b=4
n=250

X=[a+(b-a)*k/n for k in range(n+1)]
Y=[5*x+4 for x in X]

title("Réprésentation de la fonction $x\mapsto 5*x+4$")
ylim(-40, 40)
xlim(-4, 4)
#Axe du repère
plot([0, 0], [-40, 40], 'k')
plot([-40, 40], [0,0], 'k')
plot(X, Y, 'r')
line1,=plot(-0.80029296875,0, marker="o", color="red")
plt.legend([line1],["Solution"])
grid(True)
show()

NUM_FRAME=[n//4, n//2, 3*n//4, n, n+1]
for num_frame in NUM_FRAME : 
    title("Réprésentation de la frame "+str(num_frame)+" la fonction $x\mapsto 5*x+4 $")
    ylim(-40, 40)
    xlim(-4, 4)
    plot([0, 0], [-40, 40], 'k')
    plot([-40, 40], [0,0], 'k')
    plot(X[:num_frame], Y[:num_frame], 'r')
    line1,=plot(-0.80029296875,0, marker="o", color="red")
    plt.legend([line1],["Solution"])
    grid(True)
    show()

fig = figure() #On donne le nom 'fig' à la fenêtre

f, =plot([], [], 'r', lw=3, label="$f(x)=5*x+4$") #On donne le nom 'f' à la courbe de la fonction et on précise toutes les options voulues

title("Représentation de la fonction $5*x+4$ sur $[-4 ; 4]$") #On met un titre au graphique
ylim(-40, 40) #On précise le champ des abscices
xlim(-4, 4) #On précise le champ des ordonées
plot([0, 0], [-40, 40], 'k')
plot([-40, 40], [0,0], 'k')
plot(-0.80029296875,0, marker="o", color="red")
legend() #On demande l'affiche des label
grid(True) #On demande l'affichage de la grille

def MonAnimation(num_frame) : 
    f.set_data(X[0:num_frame], Y[0:num_frame])#Pour une liste Z, Z[a:b] renvoie les valeurs de Z entre les positions a et b
    return ()
ani = animation.FuncAnimation(fig, MonAnimation, n+2)#On a n+1 frame, mais il faut rajouter la frame initiale
HTML(ani.to_jshtml())

Once Loop Reflect

Les fonctions à une seule solution dans l'intervalle de droite

On affecte une fonction mathématique à la fonction dichotomie afin de trouver la valeur de x en laquelle f(x) s'annule.

On cherche à résoudre z(x)=0 avec : z(x)=-3x+2.

On définit la fonction z(x) dans python.

#création d'une fonction mathématique

def z(x):
    return -3*x+2

On trace le graphique de la fonction afin de visualiser sa courbe et de déterminer le nombre de changements de signes qui nous donnera implicitement le nombre de solutions à z(x)=0.

#création du graphique 

x = np.linspace(-4, 4, 100)

plt.plot(x, z(x))
plt.axhline(y=0, color="black")
plt.axvline(x=0, color="black")
plt.grid(True)
plt.xlabel("x")
plt.ylabel("z(x)")
plt.title("Tracé de z(x) = -3x+2")
plt.show()

Determination de l'intervalle de la fonction à une solution dans l'intervalle de droite

On peut voir sur le graphe que la fonction admet une solution. On va alors chercher la solution dans l'intervalle de gauche[-4,0] en utilisant la méthode de recherche par dichotomie.

ATTENTION: CERTAINS FONCTIONS SONT MONOTONES ET N'ONT DONC PAS DE SOLUTIONS. IL FAUDRA DONC VÉRIFIER QUE LA/LES INTERVALLES EN QUESTION CONTIENNENT UN/DES SOLUTIONS À z(x)=0.

Placement de l'intervalle de droite sur un graphique

On peut voir sur le graphe que la fonction admet une unique solution. On va alors chercher la solution à f(x) = 0 dans l'intervalle [0,4] en utilisant la méthode de recherche par dichotomie.Plaçons déjà l'intervalle (de droite) qui contient l'unique solution de la fonction z(x)=0.

#création du graphique du premier intervalle

x = np.linspace(0, 4, 100)

plt.plot(x, z(x))
plt.axhline(y=0, color="black")
plt.axvline(x=0, color="black")
plt.grid(True)
plt.xlabel("x")
plt.ylabel("z(x)")
plt.title("Tracé de z(x) = -3*x+2")
plt.show()

Determination de la solution

Ensuite, dans un second temps, determinons ensemble la valeur de la solution z(x)=0 grâce à la dichotomie.

#détermination de la première solution et de l'intervalle

x1 = dichotomie(z, 0, 4, 0.001)

print(x1)

a = 0
b = 2.0
a = 0
b = 1.0
a = 0.5
b = 1.0
a = 0.5
b = 0.75
a = 0.625
b = 0.75
a = 0.625
b = 0.6875
a = 0.65625
b = 0.6875
a = 0.65625
b = 0.671875
a = 0.6640625
b = 0.671875
a = 0.6640625
b = 0.66796875
a = 0.666015625
b = 0.66796875
a = 0.666015625
b = 0.6669921875
('La solution à f(x) = 0 est:', 0.66650390625)

Placement de la solution sur un graphique

Puis, dans un dernier temps, plaçons cette solution sur l'intervalle (de droite) qui le contient. Mais également sur la courbe au complète pour un meilleur aperçu.

#création du graphique de la premiere solution

x = np.linspace(0, 4, 100)

plt.plot(x, z(x))
line1, = plt.plot(0.66650390625,0, marker="o", color="red")
plt.axhline(y=0, color="black")
plt.axvline(x=0, color="black")
plt.grid(True)
plt.xlabel("x")
plt.ylabel("z(x)")
plt.title("Tracé de z(x) = -3x+2")
plt.legend([line1],["Solution"])
plt.show()

#création du graphique 

x = np.linspace(-4, 4, 100)

plt.plot(x, z(x))
line1, = plt.plot(0.66650390625,0, marker="o", color="red")
plt.axhline(y=0, color="black")
plt.axvline(x=0, color="black")
plt.grid(True)
plt.xlabel("x")
plt.ylabel("z(x)")
plt.title("Tracé de z(x) = -3*x+2")
plt.legend([line1],["Solution"])
plt.show()

Les animations de z(x) = -3*x+2

Après plusieurs tests, voici quelques animations intéréssantes que nous proposons pour la fonction z(x)=-3*x+2.

a=-4
b=4
n=250

X=[a+(b-a)*k/n for k in range(n+1)]
Y=[-3*x+2 for x in X]

title("Réprésentation de la fonction $x\mapsto -3*x+2$")
ylim(-40, 40)
xlim(-4, 4)
plot([0, 0], [-40, 40], 'k')
plot([-40, 40], [0,0], 'k')
plot(X, Y, 'r')
line1,=plot(0.66650390625,0, marker="o", color="red")
plt.legend([line1],["Solution"])
grid(True)
show()

NUM_FRAME=[n//4, n//2, 3*n//4, n, n+1]
for num_frame in NUM_FRAME : 
    title("Réprésentation de la frame "+str(num_frame)+" la fonction $x\mapsto -3*x+2 $")
    ylim(-40, 40)
    xlim(-4, 4)
    plot([0, 0], [-40, 40], 'k')
    plot([-40, 40], [0,0], 'k')
    plot(X[:num_frame], Y[:num_frame], 'r')
    line1,=plot(0.66650390625,0, marker="o", color="red")
    plt.legend([line1],["Solution"])
    grid(True)
    show()

fig = figure() #On donne le nom 'fig' à la fenêtre

f, =plot([], [], 'r', lw=3, label="$f(x)=-3x+2$") #On donne le nom 'f' à la courbe de la fonction et on précise toutes les options voulues

title("Représentation de la fonction $-3*x+2$ sur $[-4 ; 4]$") #On met un titre au graphique
ylim(-40, 40) #On précise le champ des abscices
xlim(-4, 4) #On précise le champ des ordonées
plot([0, 0], [-40, 40], 'k')
plot([-40, 40], [0,0], 'k')
plot(0.66650390625,0, marker="o", color="red")
legend() #On demande l'affiche des label
grid(True) #On demande l'affichage de la grille

def MonAnimation(num_frame) : 
    f.set_data(X[0:num_frame], Y[0:num_frame])#Pour une liste Z, Z[a:b] renvoie les valeurs de Z entre les positions a et b
    return ()
ani = animation.FuncAnimation(fig, MonAnimation, n+2)#On a n+1 frame, mais il faut rajouter la frame initiale
HTML(ani.to_jshtml())

Once Loop Reflect

Les animations des trois fonctions en même temps

Après plusieurs tests, voici quelques animations intéréssantes que nous proposons qui combinent les trois fonctions que nous avons usé pour cette SAE afin de voir la différence entre ces dernières.

a=-4
b=4
n=250

X=[a+(b-a)*k/n for k in range(n+1)]
Z=[-3*x+2 for x in X]
F=[5*x**2-34 for x in X]
Y=[5*x+4 for x in X]


title("Réprésentation des trois fonctions en même temps")
ylim(-40, 40)
xlim(-4, 4)
plot([0, 0], [-40, 40], 'k')
plot([-40, 40], [0,0], 'k')
line1,=plot(X, Y, 'r')
line2,=plot(X,Z,'b')
line3,=plot(X,F,'g')
plot(-2.6080322265625,0, marker="o", color="orange")
plot(2.6080322265625,0, marker="o", color="purple")
plot(-0.80029296875,0, marker="o", color="green")
plot(0.66650390625,0, marker="o", color="red")
plt.legend([line1,line2,line3],["5x+4","-3x+2","5x^2-34"])
grid(True)
show()

NUM_FRAME=[n//4, n//2, 3*n//4, n, n+1]
for num_frame in NUM_FRAME : 
    title("Réprésentation de la frame "+str(num_frame)+" la fonction $x\mapsto -3*x+2 $")
    ylim(-40, 40)
    xlim(-4, 4)
    plot([0, 0], [-40, 40], 'k')
    plot([-40, 40], [0,0], 'k')
    line1,=plot(X[:num_frame], Y[:num_frame], 'r')
    line2,=plot(X[:num_frame], Z[:num_frame], 'b')
    line3,=plot(X[:num_frame], F[:num_frame], 'g')    
    plot(-2.6080322265625,0, marker="o", color="orange")
    plot(2.6080322265625,0, marker="o", color="purple")
    plot(-0.80029296875,0, marker="o", color="green")
    plot(0.66650390625,0, marker="o", color="red")
    plt.legend([line1,line2,line3],["5x+4","-3x+2","5x^2-34"])
    grid(True)
    show()

a=-4
b=4
n=250

X=[a+(b-a)*k/n for k in range(n+1)]
F=[5*x**2-34 for x in X]
Y=[5*x+4 for x in X]
Z=[-3*x+2 for x in X]

###############################################
#        INITIALISATION DE LA FENETRE         #
###############################################
fig = figure()

l, =plot([], [], 'r', lw=3, label="$l(x)=5*x**2-34(x)$")
m, =plot([], [], 'b', lw=3, label="$m(x)=5*x+4(x)$")
o, =plot([], [], 'g', lw=3, label="$n(x)=-3*x+2(x)$")

title("Représentation des fonctions à plusieurs solutions, une solution dans l'intervalle de gauche et une seule dans l'intervalle de droite sur $[-4 ; 4]$") 
ylim(-40, 40) 
xlim(-4, 4)
plot([0, 0], [-40, 40], 'k')
plot([-40, 40], [0,0], 'k')
plot(-2.6080322265625,0, marker="o", color="orange")
plot(2.6080322265625,0, marker="o", color="purple")
plot(-0.80029296875,0, marker="o", color="green")
plot(0.66650390625,0, marker="o", color="red")
legend()
grid(True)


###############################################
#           MA FONCTION D'ANIMATION           #
###############################################
def MonAnimation(num_frame) : 
    print("\rCalcul en cours : "+str(round((num_frame+1)/(n+2)*100, 2))+"%", end='   ')
    l.set_data(X[0:num_frame], F[0:num_frame])
    m.set_data(X[0:num_frame], Y[0:num_frame])
    o.set_data(X[0:num_frame], Z[0:num_frame])
    return ()

###############################################
#     CREATION ET AFFICHAGE DE L'ANIMATION    #
###############################################
ani = animation.FuncAnimation(fig, MonAnimation, n+2, interval=25)
HTML(ani.to_jshtml())

Calcul en cours : 100.0%   

Once Loop Reflect

Les limites de la méthode de dichotomie

Le principal avantage de cette méthode est sa robustesse, puisque si f est continue, alors l'algorithme est théoriquement convergent (la taille de l'intervalle de recherche tend vers zéro). Le principal défaut de l'algorithme est que seul le signe de f est utilisé, ce qui mène à une convergence plutôt lente, c'est-à-dire quasiment linéaire. La méthode de Newton, qui utilise la valeur de f ainsi que la valeur de la pente de f, est, quand elle converge, bien plus rapide.

Cette méthode d'une grande solidité nécessite cependant de connaître à chaque étape le signe de f(m). Dans quelques cas, il peut arriver que la valeur de f(m) soit si proche du 0 que le logiciel de calcul ne permette plus de déterminer le signe de f(m) (il assimile f(m) à 0). L'algorithme risque alors de conduire à l'élimination d'une moitié de l'intervalle et à la convergence vers une valeur éloignée de la solution. D'une manière plus générale, la détermination du signe de f(m) peut se révéler très difficile voire impossible, même en augmentant la précision du calcul du logiciel.

Cependant, aucune méthode n'est pas défaillante. Elles ont tous des avantages et inconvénients donc nous ne pouvons pas mettre un terme à ce problème.

Merci de votre attention. Nous arrivons à terme de ce projet dont nous avons mis énormèment de temps mais également d'effort à le réaliser. Ce ne fut pas une partie de plaisir mais ce fut très intéressant et ludique. Nous avons appris beaucoup de choses à travers ce projet, et nous espérons en apprendre davantage.